//
// Created by luoen on 19-7-5.
//

#include <string.h>
#include <android/log.h>
#include "sample_array.h"

jstring Java_com_algorithm_practice_fragment_ArrayFragment_sort(JNIEnv * env, jobject ctx, jstring src, jbyte type, jbyte method) {
    if (NULL == src) {
        return NULL;
    }
    const char * num_str = (*env)->GetStringUTFChars(env, src, NULL);
    if (NULL == num_str) {
        return src;
    }
    jsize num_size = (*env)->GetStringUTFLength(env, src);
    if (num_size <= 1) {
        jstring ret = (*env)->NewStringUTF(env, num_str);
        (*env)->ReleaseStringUTFChars(env, src, num_str);
        return ret;
    }
    char dst[num_size];
    int i = 0;
    for (; i < num_size; ++i) {
        dst[i] = num_str[i];
    }
    dst[num_size] = '\0';
    switch (method) {
        case 0:
            array_bubble_sort(dst, num_size, type);
            break;
        case 1:
            array_select_sort(dst, num_size, type);
            break;
        case 2:
            array_insert_sort(dst, num_size, type);
            break;
        case 3:
            array_merge_sort(dst, num_size, type);
            break;
        case 4:
            array_quick_sort(dst, num_size, type);
            break;
        case 5:
            array_heap_sort(dst, num_size, type);
            break;
        default:
            break;
    }
    __android_log_print(ANDROID_LOG_INFO, "sample_array", "type=%d,retStr=%s", method, dst);
    (*env)->ReleaseStringUTFChars(env, src, num_str);
    return (*env)->NewStringUTF(env, dst);
}

void array_bubble_sort(char* src, int size, char type){
    int i = 0;
    int j = 0;
    for (; i < size; ++i) {
        j = i + 1;
        for (;j < size; ++j) {
            char ci = src[i];
            char cj = src[j];
            if ((ci > cj && type == 0) || (ci < cj && type != 0)) {
                src[i] = cj;
                src[j] = ci;
            }
        }
    }
}

void array_select_sort(char* src, int size, char type){
    int i = 0;
    int j = 0;
    int m = 0;
    for (; i < size; ++i) {
        m = i;
        j = i + 1;
        char ci = src[i];
        for (;j < size; ++j) {
            char cj = src[j];
            if ((ci > cj && type == 0) || (ci < cj && type != 0)) {
                m = j;
                ci = cj;
            }
        }
        if (m != i) {
            char tmp = src[m];
            src[m] = src[i];
            src[i] = tmp;
        }
    }
}

void array_insert_sort(char* src, int size, char type){
    int j = 0;
    int i = 1;
    for (; i < size; ++i) {
        char ci = src[i];
        for (; j >= 0; --j) {
            char cj = src[j];
            if ((ci < cj && type == 0) || (ci > cj && type != 0)) {
                src[j+1] = cj;
                src[j] = ci;
            } else {//比较之后没有后移就说明插入的值位置已经确定，则退出当前循环
                break;
            }
        }
        j = i;
    }
}

void array_merge_sort_imp(char* src, char* tmp, int start, int size, char type) {
    if (size <= 1) {
        return;
    }
    int mid = size / 2;
    int l_start = start;
    int l_end = start + mid;
    int r_start = start + mid;
    int r_end = start + size;
    array_merge_sort_imp(src, tmp, l_start, l_end - l_start, type);
    array_merge_sort_imp(src, tmp, r_start,  r_end - r_start, type);
    int tmpIndex = start;
    int cp_size = start + size;
    while (tmpIndex < cp_size) {
        if (l_start == l_end) {//左边移动到终点直接把右边的值复制到tmp后面
            tmp[tmpIndex++] = src[r_start++];
        } else if (r_start == r_end) {
            tmp[tmpIndex++] = src[l_start++];
        } else if (src[l_start] > src[r_start]) {
            if (type != 0) {//降序
                tmp[tmpIndex++] = src[l_start++];
            } else {
                tmp[tmpIndex++] = src[r_start++];
            }
        } else {
            if (type != 0) {
                tmp[tmpIndex++] = src[r_start++];
            } else {
                tmp[tmpIndex++] = src[l_start++];
            }
        }
    }
    tmpIndex = start;
    for (; tmpIndex < cp_size; ++tmpIndex) {
        src[tmpIndex] = tmp[tmpIndex];
    }
}

void array_merge_sort(char* src, int size, char type){
    char temp[size];
    array_merge_sort_imp(src, temp, 0, size, type);
}

void array_quick_sort_imp(char* src, int start, int size, char type) {
    if (size <= 1) {
        return;
    }
    int p_size = start + size - 1;
    char pivot = src[p_size];
    int i = start;
    int j = start;
    for (; j < p_size; ++j) {
        if ((type != 0 && src[j] > pivot)
        || (type == 0 && src[j] < pivot)) {
            char tmp = src[j];
            src[j] = src[i];
            src[i] = tmp;
            ++i;
        }
    }
    src[p_size] = src[i];
    src[i] = pivot;

    array_quick_sort_imp(src, start, i - start, type);
    array_quick_sort_imp(src, i + 1, p_size - i, type);
}

void array_quick_sort(char* src, int size, char type) {
    array_quick_sort_imp(src, 0, size, type);
}

void array_heap_sort_heapify(char* src, int size, int i/*start node*/, char type) {
    if (type == 0) {//构建大顶堆
        while (1) {
            int max = i;
            int left = i * 2;
            int right = left + 1;
            if (left <= size && src[left-1] > src[i-1]) {
                max = left;
            }
            if (right <= size && src[right-1] > src[max-1]) {
                max = right;
            }
            if (max == i) {
                break;
            }
            char parent = src[i-1];
            src[i-1] = src[max-1];
            src[max-1] = parent;
            i = max;
        }
    } else {//构建小顶堆
        while (1) {
            int min = i;
            int left = i * 2;
            int right = left + 1;
            if (left <= size && src[left-1] < src[i-1]) {
                min = left;

            }
            if (right <= size && src[right-1] < src[min-1]) {
                min = right;
            }
            if (min == i) {
                break;
            }
            char parent = src[i-1];
            src[i-1] = src[min-1];
            src[min-1] = parent;
            i = min;
        }
    }
}

void array_heap_sort_build_heap(char* src, int size, char type) {
    int i = size / 2;
    for (; i >= 1 ; --i) {
        array_heap_sort_heapify(src, size, i, type);
    }
}

void array_heap_sort(char* src, int size, char type) {
    array_heap_sort_build_heap(src, size, type);
    int i = size - 1;
    for (; i > 0; --i) {
        char tmp = src[i];
        src[i] = src[0];
        src[0] = tmp;
        size--;
        array_heap_sort_build_heap(src, size, type);
    }
}